package com.smday.tree;

import org.omg.PortableServer.RequestProcessingPolicy;

import java.util.*;

/**
 * @author Summerday
 */
public class BST<E extends Comparable<E>> implements Tree<E>{

    protected TreeNode<E> root;
    protected int size = 0;

    public BST() {
        super();
    }
    public BST(E[] objects){
        for (E object : objects) {
            add(object);
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new InorderIterator();
    }

    @Override
    public void clear() {
        root = null;
        size = 0;
    }
    @Override
    public boolean search(E e) {
        TreeNode<E> curr = root;
        while(curr!=null){
            if(e.compareTo(curr.element)<0){
                curr = curr.left;
            }else if(e.compareTo(curr.element)>0){
                curr = curr.right;
            }else {
                return true;
            }
        }
        return false;
    }

    @Override
    public boolean insert(E e) {

        if(root == null){
            root = creatNewNode(e);
        }else {
            TreeNode<E> parent = null;
            TreeNode<E> curr = root;
            //遍历找到插入的位置的parent位置
            while(curr!=null){
                if(e.compareTo(curr.element)<0){
                    parent = curr;
                    curr = curr.left;
                }
                else if(e.compareTo(curr.element)>0){
                    parent = curr;
                    curr = curr.right;
                }
                else {
                    return false;
                }
            }
            if(e.compareTo(parent.element)<0){
                parent.left = creatNewNode(e);
            }else {
                parent.right = creatNewNode(e);
            }
            //size++
        }
        size++;
        return true;
    }

    private TreeNode<E> creatNewNode(E e) {
        return new TreeNode<>(e);
    }

    @Override
    public boolean delete(E e) {

        TreeNode<E> parent = null;
        TreeNode<E> curr = root;
        while(curr!=null){
            if(e.compareTo(curr.element)<0){
                parent = curr;
                curr = curr.left;
            }else if(e.compareTo(curr.element)>0){
                parent = curr;
                curr = curr.right;
            }else {
                break;
            }
        }
        //元素不在树中
        if(curr == null){
            return false;
        }
        //当前节点没有左子树
        if(curr.left == null){
            if(parent == null){
                root = curr.right;
            }else {
                if(e.compareTo(parent.element)<0){
                    parent.left = curr.right;
                }else {
                    parent.right = curr.right;
                }
            }
        }else {
            //当前节点有一个左子树
            TreeNode<E> parentOfRightMost = curr;
            TreeNode<E> rightMost = curr.left;
            //找到嘞右边最大的值
            while(rightMost.right!=null){
                parentOfRightMost = rightMost;
                rightMost = rightMost.right;
            }
            //赋值
            curr.element = rightMost.element;
            //判断rightMost是parentOfRightMost左or右节点,只能连接rightMost的left,因为right不可能再有元素
            if(parentOfRightMost.right == rightMost){
                parentOfRightMost.right = rightMost.left;
            }else {
                parentOfRightMost.left = rightMost.left;
            }
        }
        size--;
        return true;
    }

    @Override
    public int getSize() {
        return 0;
    }

    @Override
    public void inOrder() {
        inOrder(root);
    }

    protected void inOrder(TreeNode<E> root) {
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.element+" ");
        inOrder(root.right);
    }


    @Override
    public void postOrder() {
        postOrder(root);
    }

    protected void postOrder(TreeNode<E> root) {
        if(root ==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.element+" ");
    }

    @Override
    public void preOrder() {
        preOrder(root);
    }

    public TreeNode<E> getRoot(){
        return root;
    }

    protected void preOrder(TreeNode<E> root) {
        if(root ==null){
            return;
        }
        System.out.print(root.element+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static class TreeNode<E>{
        protected E element;
        protected TreeNode<E> left;
        protected TreeNode<E> right;

        public TreeNode(E element) {
            this.element = element;
        }
    }

    private class InorderIterator implements Iterator<E> {
        private List<E> list = new ArrayList<>();
        private int curr = 0;

        public InorderIterator(){
            inOrder();
        }

        @Override
        public boolean hasNext() {
            if(curr<list.size()){
                return true;
            }
            return false;
        }

        @Override
        public E next() {
            return list.get(curr++);
        }
        private void inOrder(){
            inOrder(root);
        }

        private void inOrder(TreeNode<E> root){
            if(root ==null){
                return;
            }
            inOrder(root.left);
            list.add(root.element);
            inOrder(root.right);

        }

        @Override
        public void remove() {
            if(curr == 0){
                throw new IllegalStateException();
            }
            delete(list.get(--curr));
            list.clear();
            inOrder();
        }
    }
}
